/*
https://leetcode.cn/problems/shortest-distance-after-road-addition-queries-ii/description/
3244. 新增道路查询后的最短距离 II
*/

class Solution {
public:
    vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {
        typedef pair<int, int> pii;
        // 用一个 set 维护当前的最短路包含哪些区间
        set<pii> st;
        // 先把初始的 i - 1 -> i 都加进来
        for (int i = 1; i < n; i++) st.insert(pii(i - 1, i));

        vector<int> ans;
        for (auto &qry : queries) {
            int l = qry[0], r = qry[1];
            // 判断这个区间是否包含最短路里的其它区间
            // 如果当前最短路里存在区间 [l', r') 满足 l' == l 且 r' < r，那么新区间 [l, r) 肯定包含它
            // 否则新区间肯定已经被包含，没有加入的必要
            auto it = st.lower_bound(pii(l, -1));
            if (it != st.end() && it->first == l && it->second < r) {
                // 踢掉所有新区间 [l, r) 包含的老区间
                while (it != st.end() && it->first < r) it = st.erase(it);
                st.insert(pii(l, r));
            }
            // 答案就是 set 的大小
            ans.push_back(st.size());
        }
        return ans;
    }
};

